package com.easy;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by Lxk on 2020/2/10.
 */
public class Solution167 {

    private Stack<Integer> stack = new Stack<>();

    private List<List<Integer>> res = new ArrayList<>();

    boolean flag = false;

    private void findCouple(int target, int pos, int[] nums) {
        if (flag) {
            return;
        }
        if (pos >= nums.length || stack.size() >= 2) {
            if (target == 0 && stack.size() == 2) {
                List<Integer> curList = new ArrayList<>();
                for (Integer val : stack) {
                    curList.add(val);
                }
                res.add(curList);
                flag = true;
            }
            return;
        }
        if (target >= nums[pos]) {
            stack.push(pos);
            findCouple(target - nums[pos], pos + 1, nums);
            stack.pop();
        }
        findCouple(target, pos + 1, nums);
    }

    public int[] twoSum(int[] numbers, int target) {
        flag = false;
        int[] arr = null;
        findCouple(target, 0, numbers);
        if (res.size() > 0) {
            arr = new int[res.get(0).size()];
            for (int i = 0; i < res.get(0).size(); i++) {
                arr[i] = res.get(0).get(i) + 1;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {2, 7, 11, 15};
        Solution167 solution167 = new Solution167();
        int[] res = solution167.twoSum(arr, 9);
        System.out.println(res);
    }

}
